Belief propagation (BP) is an iterative method to perform approximateinference on arbitrary graphical models. Whether BP converges and if thesolution is a unique fixed point depends on both the structure and theparametrization of the model. To understand this dependence it is interestingto find \emph{all} fixed points. In this work, we formulate a set of polynomialequations, the solutions of which correspond to BP fixed points. To solve sucha nonlinear system we present the numerical polynomial-homotopy-continuation(NPHC) method. Experiments on binary Ising models and on error-correcting codesshow how our method is capable of obtaining all BP fixed points. On Isingmodels with fixed parameters we show how the structure influences both thenumber of fixed points and the convergence properties. We further asses theaccuracy of the marginals and weighted combinations thereof. Weightingmarginals with their respective partition function increases the accuracy inall experiments. Contrary to the conjecture that uniqueness of BP fixed pointsimplies convergence, we find graphs for which BP fails to converge, even thougha unique fixed point exists. Moreover, we show that this fixed point gives agood approximation, and the NPHC method is able to obtain this fixed point.
展开▼
